package com.wen.Part6.GraphAlgorithm.impl;

import com.wen.Part6.DataStructure.Graph;
import com.wen.Part6.GraphAlgorithm.GraphAlgorithm;

import java.util.ArrayList;
import java.util.List;

// 栈优化的拓扑排序

public class TopSort2 implements GraphAlgorithm {
    @Override
    public Object solve(Graph g) {
        List<String> list = new ArrayList<>();
        // 入度的数组
        int[] inDegreeArray = g.getInDegreeArray();
        int size = g.getSize();
        int[] visited = new int[size];
        int[] stack = new int[size];
        int top = 0;

        // 把度为0的点加入栈中
        for (int i = 0; i < size; i++) {
            if (inDegreeArray[i] == 0){
                stack[top++] = i;
            }
        }

        while(top != 0){
            // 取出入度为0的点，访问
            int i = stack[--top];
            visited[i] = 1;
            list.add(g.index2Key(i));

            for (Integer k : g.getAccessible(i)) {
                inDegreeArray[k]--;
                if (inDegreeArray[k] == 0 && visited[k] == 0){
                    stack[top++] = k;
                }
            }
        }
        System.out.println(list);
        return null;
    }
}
